package 数据结构.章节09;

import java.util.HashSet;

/**
 * @author 挚爱之夕
 * @date 2021/10/12 - 10 - 12 - 19:28
 * @Description: 数据结构.章节09
 * @Version: 1.0
 */
public class _157_有环链表的环起点 {
    public static void main(String[] args) {
        Node head1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        head1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        Node p = check2(head1);
        System.out.println(p.val);
    }

    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    //哈希集合
    private static Node check(Node head) {
        Node p = head;
        HashSet<Node> set = new HashSet<Node>();
        while (true) {
            if (set.contains(p))
                return p;
            set.add(p);
            p = p.next;
        }
    }

    //快慢指针
    private static Node check2(Node head) {
        Node p = head;
        Node fast = head;
        Node slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                break;
        }
        //判断何种方式退出的：是否有环
        if (fast == null || fast.next == null) {
            return null;
        }
        while (p != fast) {
            p = p.next;
            fast = fast.next;
        }
        return fast;
    }
}
